11552. Расположение
В классе m учеников, из них n девочек.
Учитель, мистер X, хочет выстроить всех учеников в ряд. X считает, что девочки
из его класса очень разговорчивы. Поэтому он не хочет, чтобы две девочки
располагались рядом. Мистер X хочет знать, сколькими способами он сможет
выстроить в ряд всех учеников. Помогите ему.
Вход. Первая строка содержит
количество тестов t (1 ≤ t ≤ 105). Каждая
из следующих строк содержит два целых числа m и n (1
< n ≤ m ≤ 106).
Выход. Для каждого теста выведите ответ
по модулю 109 + 7 в одной строке.
|
Пример
входа |
Пример
выхода |
|
2 3 2 4 2 |
2 12 |
РЕШЕНИЕ
комбинаторика
Анализ алгоритма
Количество
мальчиков в классе равно b = m – n. Поскольку мальчики все различимы, число способов их выстроить равно
b! = (m – n)!
Вокруг b мальчиков
образуется b + 1 позиция, куда можно поставить девочек:
Всего девочек n. Поэтому нам следует
выбрать n различных позиций из b + 1, куда можно поставить девочек:
Если n > b
+ 1, то ответ
равен
0.
Девочки тоже различимы,
значит их можно переставлять.
Таким образом, количество
способов, которыми можно выстроить в ряд всех учеников, равно
Пример
Рассмотрим тест m = 3, n = 2.
Число мальчиков
равно b = m – n = 3 – 2 = 1. Ответ равен
= 1 * 1
* 2 = 2
Рассмотрим тест m = 4, n = 2.
Число мальчиков
равно b = m – n = 4
– 2 = 2. Ответ равен
= 3 *
2 * 2 = 12
Реализация алгоритма
Объявим массивы:
·
fact содержит факториалы чисел по модулю MOD,
·
factinv содержит обратные значения к этим факториалам по модулю MOD:
fact[n] = n!
mod 1000000007
factinv[n] = n!
-1 mod 1000000007
#define MAX 1000001
#define MOD 1000000007
ll fact[MAX], factinv[MAX];
Функция pow вычисляет степень числа по модулю: xn mod p.
ll pow(ll x, ll n, ll p)
{
if (n == 0) return 1;
if (n % 2 == 0) return pow((x * x) % p, n / 2, p);
return (x * pow(x, n - 1, p)) % p;
}
Функция
inverse находит число, обратное к x по простому модулю p.
Так как p – простое
число, то по малой теореме Ферма выполняется равенство:
xp-1 mod p = 1 для любого
1 ≤ x < p
Его можно переписать в виде (x * xp-2) mod p = 1, откуда
следует, что обратным к x является число xp-2 mod p.
ll inverse(ll x, ll p)
{
return pow(x, p - 2, p);
}
Функция Cnk вычисляет
биномиальный коэффициент по формуле:
=
ll Cnk(int n, int k)
{
return ((fact[n] * factinv[k]) % MOD * factinv[n - k]) % MOD;
}
Основная часть программы. Заполняем массивы факториалов fact и обратных факториалов factinv.
fact[0] = 1;
for (i = 1; i < MAX; i++)
fact[i] = (fact[i - 1] * i) % MOD;
factinv[0] = 1;
for (i = 1; i < MAX; i++)
factinv[i] = inverse(fact[i], MOD);
Читаем количество тестов tests.
scanf("%d", &tests);
while (tests--)
{
Читаем данные текущего теста.
scanf("%d %d", &m, &n);
Вычисляем количество мальчиков b = m – n.
b = m - n;
Вычисляем и выводим ответ по формуле:
res = ((fact[n] * fact[b]) % MOD * Cnk(b + 1, n)) % MOD;
printf("%lld\n", res);
}